package P3排序算法;

import java.util.Arrays;
//堆排序 O(nlogn) S(1) 不稳定
//最大堆 -> 最小堆
//最主要的应用场所：求前K项问题 ：100000个数据 求前10个最小项
//优先队列
public class HeapSort {
    private static int len;

    public static void main(String[] args) {
        int[] arr = {2, 6, 1, 3, 8, 4, 7, 9, 5};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        len = arr.length;
        //堆化处理O(nlogn)
        heapify(arr);
        for (int i = arr.length - 1; i >= 0; i--) {
            //(1)将最大值和区间的末尾元素进行交换
            Swap.swap(arr, 0, i);
            //(2)缩小处理区间
            len--;
            //(3)将置顶的末尾元素再进行下沉操作 将新的最大值向上放
            swiftDown(arr, 0);
        }
    }

    private static void heapify(int[] arr) {
        for (int i = arr.length - 1; i >= 0; i--) {
            swiftDown(arr, i);
        }
    }

    private static void swiftDown(int[] arr, int k) {
        while (2 * k + 1 < len) {
            int j = 2 * k + 1;  //左孩子的角标
            if (j + 1 < len && arr[j + 1] > arr[j]) {
                j = j + 1;
            }
            if (arr[k] < arr[j]) {
                Swap.swap(arr, k, j);
                k = j;
            } else {
                break;
            }
        }
    }
}
